from typing import List


class Solution:
    def ringGame(self, challenge: List[int]) -> int:
        def merge1(lst):
            """处理双向可合并的情况"""
            res = []
            for v2, m2 in lst:
                if not res:
                    res.append([v2, m2])
                    continue

                v1, m1 = res[-1]

                if m1 >= v2 and m2 >= v1:
                    res[-1][0] = min(v1, v2)
                    res[-1][1] = max(m1, m2)
                else:
                    res.append([v2, m2])
                print(v2, m2, ":", res)
            return res

        def merge2(lst):
            """处理无损合并的情况"""
            res = []
            for v2, m2 in lst:
                if not res:
                    res.append([v2, m2])
                    continue

                v1, m1 = res[-1]

                if v2 <= v1 and m2 >= m1:
                    res[-1][0] = v2
                    res[-1][1] = m2
                elif v1 <= v2 and m1 >= m2:
                    pass
                else:
                    res.append([v2, m2])
            return res

        # 预处理目标数组
        now_challenge = [[v, v] for v in challenge]

        max_val = max(challenge)
        now_bit = 1 << (max_val.bit_length())
        now_val = 0
        while now_bit > 1:
            # 当前位
            now_bit >>= 1

            if not now_bit & max_val:
                continue

            # 当前填充值
            now_val += now_bit

            print("当前位:", now_bit, "当前填充值:", now_val)

            nxt_challenge = []
            for v, m in now_challenge:
                if not m & now_bit:
                    nxt_challenge.append([min(now_val, v + now_bit), m + now_bit])
                else:
                    nxt_challenge.append([v, m])
            print("处理结果:", nxt_challenge)

            nxt_challenge = merge1(nxt_challenge)  # 处理双向可合并的情况
            # nxt_challenge = merge2(nxt_challenge)  # 处理无损合并的情况

            print("整理结果:", nxt_challenge)

            # ----- 处理已经得出结果的情况 -----
            if len(nxt_challenge) == 1:
                return nxt_challenge[0][0]

            now_challenge = nxt_challenge


if __name__ == "__main__":
    print(Solution().ringGame(challenge=[5, 4, 6, 2, 7]))  # 4
    print(Solution().ringGame(challenge=[12, 7, 11, 3, 9]))  # 8
    print(Solution().ringGame(challenge=[1, 1, 1]))  # 1

    # 自制用例
    print(Solution().ringGame(challenge=[15, 6, 15, 1]))  # 9
    print(Solution().ringGame(challenge=[5, 7, 11, 13, 14, 15]))  # 8
    print(Solution().ringGame(challenge=[15, 11, 13, 15]))  # 12
    print(Solution().ringGame(challenge=[15, 14, 15]))  # 15
    print(Solution().ringGame(challenge=[15, 10, 15]))  # 13
    print(Solution().ringGame(challenge=[15, 6, 15, 1, 15, 9, 15]))  # 9
    print(Solution().ringGame(challenge=[109, 108]))  # 109

    # 测试用例73/95
    print(Solution().ringGame(challenge=[45, 45, 4, 45, 3, 45, 45, 4]))  # 41

    print(bin(40))
